A typical database cluster includes a plurality of database servers that communicate with each other for data replication and data synchronization purposes. Let us consider an example scenario in which a first change is implemented at a first database server. In order to synchronize the first change within the database cluster, the first database server communicates the first change to other database servers within the database cluster. The first change may be communicated using, for example, total order broadcast. Total order broadcast ensures that changes are reliably communicated to all the database servers in an order in which the changes were made.
However, problems may arise in one or more of following cases:
(a) when the database servers are distributed geographically,
(b) when there is heavy load on the database servers and/or one or more communication networks coupling the database servers, and/or
(c) when there is a time lag between communications.
In the example scenario, let us consider that a multi-dimensional database key space is employed at the database cluster. A conflict of synchronization may arise when two or more database servers implement different changes at a substantially similar, similar or preferably same database key of the database key space substantially concurrently. The phrase ‘substantially concurrently’ may be defined as a scenario where a change A is implemented at a first server and a change B is implemented at a second server, and the timing of both the implementations is such that the first server does not have knowledge of the change B and/or the second server does not have knowledge of the change A.
A conventional technique of resolving conflicts of synchronization and making fault-tolerant database clusters is provided in “The Database State Machine and Group Communication Issues”, a thesis by Fernando Pedone (1999) at Ecole Polytechnique Federale de Lausanne. The thesis is incorporated herein by reference in its entirety.
The conventional technique involves navigating through the multi-dimensional database key space to match database keys, and checking whether or not a substantially similar, similar or preferably same database key is involved in different changes substantially concurrently. In addition, the conventional technique employs Optimistic Concurrency Control (OCC).
Continuing from the previous example scenario, OCC may be employed in following steps:
(a) before committing the first change, the database cluster checks whether or not a database server other than the first database server has made a change involving a substantially similar, similar or preferably same database key at which the first database server made the first change; and(b) if it is found that no database server has made a change involving the substantially similar, similar or preferably same database key, the first change is committed; otherwise, if it is found that another database server has made a change involving the substantially similar, similar or preferably same database key, the first change is discarded.
However, the conventional technique suffers from a number of disadvantages. Firstly, the multi-dimensional database key space has tree topology, and requires a large computational space for storage during operation. Secondly, the database key space related tree topology data are non-trivial to serialize and de-serialize over the communication networks. Thirdly, navigating through the multi-dimensional database key space is computationally expensive. For example, time complexity of the step of navigation may be expressed as ‘O(n2)’ in big O notation. This implies that execution of this step takes quadratic time for completion.
Therefore, there exists a need for a database cluster that is capable of facilitating a significant reduction in complexity of operations performed during synchronization of data within the database cluster.